
/** @file         xx
 *  @brief        简要说明
 *  @details      详细说明
 *  @author       Schips
 *  @date         2020/09/22
 *  @version      v1.0
 *  @copyright    Copyright By Schips, All Rights Reserved
 *
 ***********************************************************************************
 *
 *  @attention
 *                Ref : https://blog.csdn.net/guanhuhousheng/article/details/77275633
 *  @par 修改日志:
 *  <table>
 *  <tr><th>Date        <th>Version  <th>Author    <th>Description
 *  <tr><td>2020/09/22  <td>1.0      <td>Schips	   <td>创建初始版本
 *  </table>
 *
 **********************************************************************************
 */

#include "rbtree_augmented.h"
 
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
 
#define MAX_INT	 11
#define BUFFER_SIZE 7

typedef  unsigned char * key;
typedef  int    val;
 
struct user_rb_t {
	struct rb_node rbnode;
	unsigned char key[BUFFER_SIZE];
	val val;
};
 
struct rb_root root = RB_ROOT;

static void print_node(const char *event, struct user_rb_t *target);

void assign_val(val *var, val val)
{
    if(!val) return;
    *var = val;
    return ;
}

void assign_key(key var, key key)
{
	memcpy(var, key, BUFFER_SIZE);
    //*var = key;
    return ;
}

int key_compare(key a1, key a2)
{
    int ret;
	ret = memcmp(a1, a2, BUFFER_SIZE);
    //printf("k   compare, ret is [%d]%p, %p\n", ret, a1, a2);
    return ret;
}

int val_compare(val a1, val a2)
{
    int ret;
    ret = a1 - a2;
    //printf("v   compare, ret is [%d]%p, %p\n", ret, &a1, &a2);
    return ret;
}

//  创建节点
struct user_rb_t * create_user_node(key key, val val)
{
	struct user_rb_t *node;
	
	node = (struct user_rb_t *)malloc(sizeof(struct user_rb_t));
	if (NULL == node)
		return NULL;
	memset(node, 0, sizeof(struct user_rb_t));

    assign_key((node->key), key);
    assign_val(&(node->val), val);
	return node;
}
 
// 查找节点（根据key）
struct user_rb_t * user_node_find(struct rb_root *root, key key)//, val val)
{
	struct rb_node *node = root->rb_node;
	struct user_rb_t * target = NULL;
	int ret = 0;
 
	while (node) {
		target = rb_entry(node, struct user_rb_t, rbnode);

		//ret = memcmp(target->key, key, BUFFER_SIZE);
        ret = key_compare(target->key, key);//ret = val_compare(target->val, val);

		if (ret < 0) {
			node = node->rb_left;
		} else if (ret > 0) {
			node = node->rb_right;
		} else
			return target;
	}
	return NULL;
}

// 查找节点（根据val）
struct user_rb_t * user_node_find_by_value(struct rb_root *root, val val)
{
    int ret;
	struct rb_node *node;
	struct user_rb_t * target = NULL;

    printf("find with val [%x]\n", val);
	for (node = rb_first(root); node; node = rb_next(node)) {
		target = rb_entry(node, struct user_rb_t, rbnode);
        print_node("tranverse", target);
        ret = val_compare(target->val, val);
        if(!ret) 
        {
            print_node("Found", target);
            break;
        }
	}
    return target;
}
 
// 插入节点(不允许重复)
int user_rb_insert(struct rb_root *root, key key, val val)
{
	struct rb_node **new = &(root->rb_node);
	struct rb_node *parent = NULL;
	struct user_rb_t *target = NULL;
	int res = 0;
    int i;
 
	while (*new) {
		parent = *new;
		target = rb_entry(*new, struct user_rb_t, rbnode);
		//res = memcmp(target->key, key, BUFFER_SIZE);
        res = key_compare(target->key, key);//res = val_compare(target->val, val);
        
		if (res < 0) {
			new = &((*new)->rb_left);
		} else if (res > 0) {
			new = &((*new)->rb_right);
		} else
        {
            printf("same and return\n");
            printf("[%d]target->key / key:", res);
            for (i = 0; i < BUFFER_SIZE; ++i) {
               printf("[%2x/%2x] ", target->key[i],  key[i]); 
               if(i % 10 == 0) printf("\n\t");   
            }
            printf("\n");
			return false;
        }
	}
	target = create_user_node(key, val);
	if (NULL == target)
		return false;
    print_node("Insert node", target);
	// add new node
	rb_link_node(&target->rbnode, parent, new);
    printf("link\n");
	// rebalance rbtree
	rb_insert_color(&target->rbnode, root);
    printf("ic\n");
	return true;
}
 
// 删除单个节点
void user_rb_delete(struct rb_root *root, key key)
{
	struct user_rb_t *target = user_node_find(root, key);
	if (NULL != target) {
		rb_erase(&target->rbnode, root);
		free(target);
	}
}

// 根据 key 找到 对应的节点，并修改其val
int user_rb_change_val(struct rb_root *root, key key, val val)
{
	struct user_rb_t *target = user_node_find(root, key);
    if(!target) return -1;
    print_node("old node val", target);
    assign_val(&(target->val), val);
    print_node("new node val", target);
    
    return 0;
}
 
// 删除整棵红黑树
void user_rb_destroy(struct rb_root *root)
{
	struct rb_node *node = NULL, *tmp_node = NULL;
	struct user_rb_t * target = NULL;
 
    // 安全遍历
	for (node = rb_first(root); node;) {
		tmp_node = rb_next(node);
		target = rb_entry(node, struct user_rb_t, rbnode);
		rb_erase(node, root);
		free(target);
		node = tmp_node;
	}
}

static void print_node(const char *event, struct user_rb_t *target)
{
    if(!target) return ;
    printf("--%15s\t[%p] key: [%02x:%02x:%02x:%02x:%02x:%02x], val: [%04x]\t pc: 0x%10lx (%c), rb_left: %12p, rb_right: %12p\n",
            event,
            target,
                target->key[0], target->key[1], target->key[2], 
                target->key[3], target->key[4], target->key[5],
                target->val,
            target->rbnode.__rb_parent_color,
            rb_is_black(&target->rbnode) ? 'B' : 'R',
            target->rbnode.rb_left,
            target->rbnode.rb_right);
}
 
// 遍历红黑树(从小到大)
static void tranverse(struct rb_root *root)
{
	struct rb_node *node;
    struct user_rb_t *target;
    printf("tranverse\n");
	for (node = rb_first(root); node; node = rb_next(node)) {
		target = rb_entry(node, struct user_rb_t, rbnode);
        print_node("tranverse", target);
	}
}

// 遍历红黑树(从大到小)
static void tranverse_inverted(struct rb_root *root)
{
	struct rb_node *node;
    struct user_rb_t *target;
    printf("tranverse_inverted\n");
	for (node = rb_last(root); node; node = rb_prev(node)) {
		target = rb_entry(node, struct user_rb_t, rbnode);
        print_node("tranverse_inv", target);
	}
}
 
int main(int argc, char ** argv)
{
	int i, j; 
    unsigned char key_array[MAX_INT][BUFFER_SIZE];
    int val_array[MAX_INT]; 

    // 初始化一些测试值
    for(i = 0; i < MAX_INT; i++)
    {
        val_array[i] = i + 1;
        for (j = 0; j < BUFFER_SIZE; j++) {
            key_array[i][j] = j + 100 *i;
        }
    }
    
    // 插入
    printf("TEST_INSERT\n");
	for (i = 0; i < MAX_INT; i++) {
		printf("[%3d]/%d insert \n", i, MAX_INT -1);
		user_rb_insert(&root, key_array[i], val_array[i]);
		tranverse(&root); // 遍历所有节点
		printf("------END\n\n");
	}
    // 遍历所有节点
	tranverse(&root);
	tranverse_inverted(&root);
    printf("Insert done\n\n\n");

    // 查找
    user_node_find(&root, key_array[2]);
    user_node_find_by_value(&root, val_array[2]);

    printf("TEST_DELETE\n");
	for (i = 0; i < MAX_INT - 1; i++) {
		tranverse(&root);
		printf("[%3d] DELETE %3d, ", i, val_array[i]);
		user_rb_delete(&root, key_array[i]);
		printf("------END\n\n");
	}
	tranverse(&root);
    printf("Del done\n\n");

    // 修改key对应的value
    printf("Change node value to %x\n", 0xabc);
    j = 0xabc;
    user_rb_change_val(&root, key_array[i], j);
	tranverse(&root);
	
	return 0;
}
